COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\area {Artificial Intelligence}
C00020 ENDMK
C⊗;
\area {Artificial Intelligence}

\problem Theorem proving (5)
 
It has been suggested that work on theorem proving has been
shelved temporarily.  Supposing this is correct, what would be the 
reason(s) for this trend?  State your answer briefly.

\answer

i. The decade-old flurry of excitement over Robinson resolution subsided
when few effective strategies were found for constraining the
combinatorially explosive search it entails.

ii. Axiomatization of most problems is quite long and difficult, hence
AI researchers are simply not able to bring predicate calculus theorem provers to
bear on most of the problems they tackle.

iii. Many of the recent AI "expert reasoning" programs are based around
inexact plausible reasoning, rather than deduction, and therefore utilize
a theorem prover only as one resource, almost as a subroutine, rather than
as the central driving mechanism. 


\problem Production systems (5)

Comment briefly on the differences between production system
architectures when used for (a) psychological models of cognitive
skills (such as PSG) and (b) expert systems (such as MYCIN or AM).

\answer

i. Complexity of Data Structures (one working memory consisting
of a linear string of tokens, vs. a set of specially-tailored structured
DS's).

ii. Placement of permanent knowledge (only in rules, vs. distributed
between rules and data structures (the knowledge bases)).

iii. Complexity of the rules (just a couple simple operations like
pattern-matching and writing a token into memory, vs. the ability to
call on arbitrary functions, have side effects, be a meaninful chunk
of knowledge to a domain expert)

iv. Complexity of the interpreter (simple cyclic scan, vs. the ability to
bring knowledge to bear to choose the best rule to fire next)



\problem Performance (5)

Pick ONE of the pairs of programs listed below and 
contrast the approaches used in the two programs of that pair.  
In light of the superior performance of the "less intelligent" program,
defend the continued use of AI in such problem areas.
\hline
  a)	DRAGON - HEARSAY
\hline
  b)	CHESS 4.6 [or 4.5 or 4.7] - CAPS
\hline
  c)	INTERNIST [Pople's early version] - MYCIN

\answer

In all cases, the former program is more driven by tables of low-level
knowledge, while the latter is more driven by inferencing off a knowledge
base of high-level information. E.g., Dragon uses Markov processes to
simulate speech at a low level, Chess 4.6 has some of its chess
information microcoded into the Cyber; Internist is built around tables
of symptom-disease correlations. The defense ofthe AI approach comes
by way of the following picture

|              x
|
|
|                    .
|
|
|
|
|               .
|
|
|
|           .
|           x
|
|        .
|
|
|        x
|   .
|
|.  x
+x-------------------------------------

The conventional non-AI approaches (x) such as microcoding can buy you
a hefty linear factor against the conbinatorial explosion, but only a linear
factor. Ultimately, such programs will not be able to be extended except
at an exponentially increasing cost.  The current AI programs, wallowing
LISP behemoths by comparison, are initially more costly (perform poorer),
but ultimately we expect that they have chipped away at the exponent in
the problem, that eventually (as machines and problems attacked grow) the
curves will cross, and AI programs will perform better.  A possible example
of this behavior already may be seen with the Dendral program for enumerating
structural isomers of a given compound.


\problem Choice of Task Domain (9)

Order the tasks below by the time it will take to produce
commercial robots to do them.  State the general principles you use to
make the ordering and explain any exceptions.
\hline
	Planning a meal
\hline
	Cooking a meal
\hline
	Serving a meal
\hline
	Teaching arithmetic
\hline
	Teaching soccer
\hline
 	Teaching (about) Shakespeare

\answer

The sensorimotor coordination required to walk is far beyond what
we can handle now. Thus soccer, and to a lesser extent serving a
meal, and to a lesser extend cooking a meal, are quite a long ways away.
Certain limited forms of cooking, those involving very few motions,
will be the first of these to arrive.  The more intellectual tasks
are certainly bound to precede all of these physical ones. A great deal
of thought has gone into arithmetic, and is going on even now with CAI efforts.
Thus that may be the first out of the six tasks to be successfully carried
out automatically. Planning a meal requires somuch less real-world knowledge
than teaching Shakespeare that it will come about much sooner.
So our ordering is 2, 3/4, 5, 1, 6, 3/4.

\problem Concepts (9)

Briefly define each of the following AI concepts 
and methods, and give a one or two sentence description of the conditions 
under which it is relevant:
\hline
	actors
\hline
	alpha-beta technique
\hline
	British Museum algorithm
\hline
	goal-directed search
\hline
	LISP
\hline
	Simon's ant

\answer

i. "actors" is are modular units of representation, as developed by
Carl Hewitt of MIT, and function by message-passing. They are appropriate
to coordinating a large network of simple processes.

ii. "αβ technique" refers to a tree-pruning procedure for cutting down the
amount of nodes necessary to expand when carrying out a minimax search
in an AND/OR tree. It is usually preferable to a blind minimax search.

iii. "British Museum algorithm" refers to an exhaustive search, and is
relevant only when nothing else is available, or for tiny problems.

iv. "goal-directed search" refers to the policy of always reexamining the
goal during a search, and trying to choose the next node to expand in that
way. It is generally useful whenever a sense of direction toward
the goal is possible.

v. "Simon's any" refers to the behavior of an ant crawling on a beach: it
appears to follow a very complex path, but when we look closer we see that
it was really just avoiding obstructions, that the complexity was in the
environment, not in the performer.


\problem Games (27)

Consider the following problem:
\hline {\sl
	You and an opponent are facing 11 stacks of pennies, of heights
    11,10,9,...,1.  You will alternate moves, removing pennies, and
    each time someone takes the final penny in a stack his OPPONENT
    will receive one point.  During his turn, each player must remove
    three pennies (three from one pile, two from one pile and one from
    another, or one each from three separate piles).  What should be
    your first move?  (Assume that your opponent will play perfectly,
    that you are trying to maximize the number of points you will
    receive, that your program can have as much time and space as it
    calls for, etc.)}
\hline

\noindent (a) [10 points] Sketch the body of a recursive program to solve
this problem.  You may omit the details, and use math notation and concepts
liberally.

\noindent (b) [7 points] Clean up the above sketch: fill in the details, such
as the base steps of the recursion, the initialization of any necessary variables
and data structures, etc.

\noindent (c) [2 points] What language might be appropriate to implement this
program in (very briefly mention why)? 
(Discuss this, don't try to rewrite your program)

\noindent (d) [4 points] Assume that, rather than being infallible, your
opponents are many and varied in their skill. How might "intelligence" be
inserted into the program so that it might attain very high scores?
(Discuss this, don't try to modify your program)

\noindent (e) [4 points] How might a software analogue of "caching" be used
to improve the program's efficiency?  (If you prefer, you may
answer this question using the software analogue
of any other hardware concept.)
(Discuss this, don't try to modify your program)

\answer

(a) 
  Best(S, par) ≡  max  [par x Best(S with Si Sj Sk decremented by 1, -par)]
		i,j,kεS

where S is the list of pile heights; initially S=(11 10 9 8 7 6 5 4 3 2 1).
where par is the parity, which is 1 when you play, -1 when opponent plays.
where we assume that the maximal i,j,k will be bound and available at the
end of calling Best; thus their final value dictates the initial move,
and the final value returned by Best is the score (hopefully positive!) we
can expect to obtain against a perfect opponent.

(b)
S ← (11 10 9 8 7 6 5 4 3 2 1)
par ← 1
Move ← (0 0 0)

Best(S, par) ≡
	Tempscore ← 0
	∀SiεS, if Si<0 then return -999999999
	       else if Si=0 then 
			Tempscore← Tempscore - par
			Remove Si from S
	if Sigma(Si)<3 then 
	     i
			M={i | SiεS}
			Return Tempscore - [ par x length(S) ]
	Move ← (i j k) maximizing the quantity
			Tempscore +  [par x Best(S with Si Sj Sk decremented, -par)]
		       which maximal quantity is Returned as the value for this function.

As above, the value of the top-level call of Best will be the expected
final score, and the value of Move will be the pile-numbers of the
piles from which the three coins should initially be removed.

(c) Lisp comes to mind, not only because this is the AI section of the exam, but
also because of its ability to handle recursion, list deletions, forall/foreach
mappings, etc. In short, translating the (b) program into Lisp would take but
a small fraction of the time it would take for Basic, Cobol, and other straw
men. Also, the debugging capabilities in modern Lisp languages make it very
easy to check the partially-complete program, to change the sign in front of
"par" and try it again, etc., compared to compiled languages (and interpretive
ones without a "break package").

(d) Modelling the user sems appropriate.  We can imagine creating and
using a large knowledge base of models for various types of players
(neophyte, mathematician, impatinet, etc.), and trying to quickly ascertain
which "stereotype" our current player falls into.  Each class would have
its own special weaknesses which could be taken advantage of.  In addition,
a special model could be accreted for each individual who played the
system, and it could thereby know and exploit his own weaknesses (e.g.,
laying a trap which a perfect opponent would ignore).

(e) The results of some of the searches may be stored in a place where they
can be accessed when later called for again, so as to avoid re-computing them.
As a simple example, consider the situations where after 4 moves, ther
were 16 distinct ways to reach the identical state of the piles. It would be
a waste to compute n↑n where n! will do. Also, there are isomorphs that
arise due to the fact that what matters is merely the SET of pile heights;
thus (1 2 0 4 0 0 4 5 5 9 11) is the same as (1 2 0 0 0 0 5 5 9 4 11).
We can imagine storing the results under the SORTED list of pile heights,
in this case (0 0 0 0 1 2 4 4 5 5 9 11). After solving this once, the second
time we'd have the program check for such an entry, it would find and return it immediately,
without recomputing it.